package NowCoder.DynamicPlanning;
import java.util.*;
/**
 * WY28 跳石板
 * 中等  通过率：14.75%  时间限制：1秒  空间限制：32M
 * 知识点
 * 贪心
 * 动态规划
 * warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
 * 描述
 * 小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3.......
 * 这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
 * 例如：
 * N = 4，M = 24：
 * 4->6->8->12->18->24
 * 于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板
 * 输入描述：
 * 输入为一行，有两个整数N，M，以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)
 * 输出描述：
 * 输出小易最少需要跳跃的步数,如果不能到达输出-1
 *
 * 示例1
 * 输入：
 * 4 24
 * 复制
 * 输出：
 * 5
 *
 * https://www.nowcoder.com/practice/4284c8f466814870bae7799a07d49ec8?tpId=122&tqId=33674&ru=/exam/oj
 */
public class 跳石板_WY28 {
    //TODO:请重新做这一道题

    /**
     * 动态规划
     * 思路：定义jump[]数组，jump[n]表示调到整数n所用的最小步数。
     * 初始化，jump[n ~ m] 为-1。
     * 状态转移方程，对第k步，我们找到所有满足jump[x] == k - 1的石板，然后更新jump数组，更新的方法是从jump[x]向后跳一步y，y是x的除1和x的约数，即
     * if (jump[x + y] != -1) jump[x + y] = jump[x] + 1
     * 从步数为1开始迭代。
     * 结束的条件，为jump[M] != -1，表示找到了到达整数M石板的最小步数；
     * 或者 对当前步数k找不到满足(N <= x <= M) jump[x] == k - 1的石板，等价于说我们要找的石板越界了，第k-1步能到达的石板肯定大于M，你仔细想一想。
     */
    public static int jumpTimes(int N, int M) {
        // jump数组表示调到jump[i]所用的最大步数
        int[] jump = new int[M + 1];

        // 初始化jump数组为-1
        for (int i = N; i <= M; ++i) {
            jump[i] = -1;
        }

        int step = 1;
        jump[N] = 0;

        // printState(jump, N);
        while (jump[M] == -1) {
            int max_step = Integer.MIN_VALUE;

            for (int cur = N; cur <= M; ++cur) {
                if (jump[cur] > max_step)
                    max_step = jump[cur];

                if (jump[cur] < step - 1)
                    continue;
                    // 找到step-1步所能走到的石板
                else if (jump[cur] == step - 1) {

                    for (int k = 2; k <= Math.sqrt(cur); ++k) {
                        // System.out.println("cur = " + cur + ", k = " + k);
                        // 找到约数k，更新jump数组
                        if (cur % k == 0) {
                            if (cur + k <= M && jump[cur + k] == -1) jump[cur + k] = step;
                            if (cur + cur / k <= M && jump[cur + cur / k] == -1) jump[cur + cur / k] = step;
                        }
                    }
                } else {
                    continue;
                }
            }

            // 当前步数和jump数组中最大的步数相差2，
            // 等价于是找不到step-1步所能走到的石板了，因为越界了，所以循环结束
            if (step - max_step > 1)
                break;

            step++;
            // printState(jump, N);
        }

        // printState(jump, N);
        return jump[M];
    }

    // 打印状态数组
    private static void printState(int[] jump, int N) {
        System.out.println("JUMP");
        for (int i = N; i < jump.length; ++i) {
            System.out.printf("%5d ", i);
        }
        System.out.println();
        for (int i = N; i < jump.length; ++i) {
            System.out.printf("%5d ", jump[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int result = jumpTimes(N, M);
        System.out.println(result);
    }
}
